本场链接:Codeforces Round #593
闲话:本场最快的做出的人只有10多分钟,拿到了200名,如果能出就能到200名.而很慢出的(我vp的结果)就只有3000多了.而且本场我思路全都跑歪了,就很蛋疼,时间上拖了很久.
A. Stones
题目大意:一共有三堆石子,分别有个石子在里面,每次你可以选择如下两种操作方式:
①从第一堆拿一个,第二堆拿两个
②从第二堆拿一个,第三堆拿一个.
如果数量不够,则不能执行操作.初始手上没有石子,问手上最多有多少个石子.
数据范围:
A题思路
首先,设第一种操作执行了次,第二种执行了次.那么结束后,手上应该拿到了个石子,并且数量关系应该要满足:和以及.我最开始的想法就是,这三个表达式很显然可以合并得到:,左半边就是答案,那不就是说右半边是答案的上界吗.不过样例就直接把这个想法打回原形了,因为这个上界并不是一个确切的上界,不是一定能取到的.再往这个方向上想也没有什么突破口.
因为这个题目的数据量相当小,可以考虑暴力枚举所有和的取值,并判断是否合法,最后更新答案即可.这样就不用去管不等式是否能得到一个正确的答案了.
A题代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
int res = 0;
for(int x = 0;x <= 100;++x)
{
for(int y = 0;y <= 100;++y)
{
if(x > a || c < 2 * y || b - 2 * x - y < 0) continue;
// cout << x << " " << y << endl;
res = max(res,3 * (x + y));
}
}
printf("%d\n",res);
}
return 0;
}
B. Alice and the List of Presents
题目大意:一共有种礼物,个盒子.要把这个礼物分配到每个盒子里去.要求满足以下几个条件:
①一个盒子里不能有相同品种的礼物
②每个盒子都视作是不同的(就是说你把一号物品放在第一个盒子里和放在第二个盒子里是不同的)
③每一种礼物都至少要放入一个盒子.
举一个具体的例子,如果有一种礼物,三个盒子的话,分配方案应该是这样的(其中表示空):
100
010
001
110
101
011
111
总计七种
问在给定的条件下,一共有多少种分配方案.由于数字很大,对取模.
数据范围:
B题思路
这个题模拟完样例之后就大概的可以想到,对一个物品多个箱子的情况,答案应该就是统计这样的一个和:个箱子里取一个的方案数,个箱子里取两个的方案树...一直到个箱子里取个的方案数.这很容易联想到组合数的求和公式,即.对应到我们这个题目里来,其实就是多了一个不选的情况,所以对于只有一种的情况来说,答案就应该是.
想完了这个问题,再考虑说有多个的时候怎么办.可以把每个元素的添加看成是一步一步来的,因为每种礼物都至少要在某一个盒子里出现过,所以不会有说后者顶上前者一个完全空盒子的情况.假如说我已经构造了一个只有第一种和只有第二种礼物的方案,那么一个只有第一种礼物的方案可以和任意的一个一个只有第二种礼物的方案直接相加结合,就是说对于一个只有第一种礼物的方案,他有又有多个选择,每个选择就是找一个只有第二种方案的跟他相加,这个过程是相互独立的,就适用乘法原理.
设是只有一种礼物的方案数,那么.而最后的答案,一共有种礼物,每种礼物都是独立的,故.两个过程都可以用快速幂求出来,直接计算结果即可.
B题代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
ll qpow(ll a,ll b)
{
ll res = 1 % MOD;
while(b)
{
if(b & 1) res = (res % MOD * a % MOD) % MOD;
a = (a % MOD * a % MOD) % MOD;
b >>= 1;
}
return res;
}
int main()
{
ll n,m;scanf("%lld%lld",&n,&m);
ll res = qpow(2,m);
res = (res % MOD - 1) % MOD;
res = qpow(res,n);
printf("%lld",res);
return 0;
}
C. Labs
给定一个正整数,构造一个的矩阵.定义一个函数表示这个对这个矩阵行来说,其内部每一个元素,在行中有多少个元素比他小的总和.不能有.试构造一个,使所有可能的的最小值最大的矩形的具体方案.
数据范围:
C题思路
一看到最小值最大,其实方向就比较明确了,可能是二分答案,或者贪心之类的.
推敲之后可以想到想要使这个最小值最大,就是让所有的的值尽可能的平均,想要他尽可能的平均,就是要让值均匀分配.为了方便构造,先把要取的数的矩阵画出来,下面是一个的矩阵:
我最开始的思路很简单,你不是要平均分配吗,那我就构造的时候,就第一行选第一个,第二行选第二个...循环取下去,这样看起来是大小平均了,然后就了.为什么呢,因为对于循环取数而言,他可能会破坏掉相对大小关系,导致不平均.正确的做法应该是:构造第一行的时候,我在取数的矩阵里先取第一行的最大值,再取第二行的最小值,之后取第三行的最大值....这样一直循环下去.这样做的好处就是我跟其他行能取到的和别的行过来我这取到的是平均的,保证了数量基本相等.
为什么这样交替选择最大值最小值就最好呢,最好意味着最平均.对于取数矩阵里的每一行来说,我第一行的最大值是必然小于第二行的最小值的,这个关系是依次递进的.假设说是一个的,就跟上图一样,对于我构造的第一行来说,我选择的每个最大值一定大于其他行在取数矩阵里选了这一行的数,而最小值都一定小于选了其他这一行的数.从感性的角度思考这样确实达到了平均.
关于数学上的证明,可以参考洛谷题解区的内容,1236C 题解,这种方法构造的矩阵虽然看起来不同,但是因为两行之间谁上谁下是没有区别的,所以移动一下就是题解里所说的构造方案,证明就对应起来了.
具体实现的时候,可以对取数矩阵里的每一行都设置两个变量和,取数的时候依次移动,就可以了.然后对于每一个格子来说,可以像之前的棋盘与二分图的题里写的那样,对他的坐标之和判断奇偶性来得知这一格应该放的是最大值还是最小值.
C题代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 305;
int a[N][N],L[N],R[N];
int main()
{
int n,m;scanf("%d",&n);m = n * n;
int cur = 0;
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= n;++j) a[i][j] = ++cur;
L[i] = 1,R[i] = n;
}
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= n;++j)
{
if((i + j) % 2) printf("%d ",a[j][L[j] ++]);
else printf("%d ",a[j][R[j] --]);
}
puts("");
}
return 0;
}
D. Alice and the Doll
有一个在大小的平地上移动的机器人,初始位置在,并规定他的朝向一开始是朝右的.在一个格子上,他最多只能按顺时针转动一次方向(可以不转),并且之前走过的路径不能再走.现在平地上放置个障碍物,机器人不能走到障碍物上,也不能走出这块平地.问他是否能走完整个平地上除了障碍物的所有点.只需要输出是否,不需要输出具体答案.
数据范围:
注意的大小非常大.
D题思路
这个题看起来也非常吊,既然说只是方案,那似乎可以考虑有哪些形状是必然导致失败的,但是由于说这个题目的大小实在是太大了,导致根本不可能遍历这张完整的图,判断具体是什么形状也变得非常困难.因此必须从其他方面入手.
如果说这张图上,没有任何一个障碍物的话,那么这个时候肯定就是螺旋状的移动,肯定能遍历到所有的点的,但是如果有障碍物挡在下一步上,这个时候就只能转向了.假如说我转向了,我必然会损失一部分的路径,因此我是能不转向就不转向.注意这不是说有障碍物就不能走了,而是说如果转向了,可能会有一段路是走不了了的,比如下面这个情况:
显然绿色块会因为那个转向而根本无法到达,但是这不意味着有障碍物就无法遍历完了,假如说绿色块全是障碍物,这个时候又显然是正确的了.
所以每次移动的时候,肯定都是除非必须要转了,否则一定不转.那与我移动路径有关的,其实就只有我当前路径上,最近的一个障碍物的坐标是多少.因此,可以做一个邻接表进行维护,即抠出所有行上有哪些列有障碍物以及所有列上有哪些行有障碍物.对于四个移动方向的路径,依次去二分确定最近障碍物的坐标,根据差值算出总的路径之和,最后判断是否走完了全图,就可以了.复杂度就从到了.在具体实现的时候,还需要维护一下当前矩形的边缘坐标,因为对于螺旋形走法来说,下一次的最大值就会减少了,具体看代码即可.
这题还有一个坑,下面这组数据:
5 5 22
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4
1 5
2 5
3 5
4 5
5 5
具体坑在,如果第一次不是往右走的,第一次移动的判断就会使得机器人原地踏步,但是这一次并不是就是终点,他是可以旋转一次往下走的.把这种情况特判掉就完了.
D题代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int n,m,k;
vector<int> R[N],C[N];
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i = 1;i <= k;++i)
{
int x,y;scanf("%d%d",&x,&y);
R[x].push_back(y);
C[y].push_back(x);
}
for(int i = 1;i <= n;++i) sort(R[i].begin(),R[i].end());
for(int i = 1;i <= m;++i) sort(C[i].begin(),C[i].end());
int x = 1,y = 1,dir = 1;//cur state
int bdxl = 0,bdxr = n + 1,bdyl = 0,bdyr = m + 1;
/*
bdxl:x坐标的上边界,不能比他还往上
bdxr:x坐标的下边界,不能比他还往下
bdyl:y坐标的左边界,不能比他还往左
bdyr:y坐标的右边界,不能比他还往右
*/
ll res = 1,flag = 0;
while(1)
{
int ex = 0,ey = 0;
if(dir == 1)
{
//right
ex = x;ey = lower_bound(R[x].begin(),R[x].end(),y) - R[x].begin();
if(ey == R[x].size()) ey = bdyr - 1;
else ey = min(bdyr - 1,R[x][ey] - 1);
dir = 2;
bdxl = x;
}
else if(dir == 2)
{
//down
ex = lower_bound(C[y].begin(),C[y].end(),x) - C[y].begin();ey = y;
if(ex == C[y].size()) ex = bdxr - 1;
else ex = min(bdxr - 1,C[y][ex] - 1);
dir = 3;
bdyr = y;
}
else if(dir == 3)
{
//left
ex = x;ey = lower_bound(R[x].begin(),R[x].end(),y) - R[x].begin() - 1;
if(ey < 0) ey = bdyl + 1;
else ey = max(bdyl + 1,R[x][ey] + 1);
dir = 4;
bdxr = x;
}
else if(dir == 4)
{
//up
ex = lower_bound(C[y].begin(),C[y].end(),x) - C[y].begin() - 1;ey = y;
if(ex < 0) ex = bdxl + 1;
else ex = max(bdxl + 1,C[y][ex] + 1);
dir = 1;
bdyl = y;
}
if(x == ex && y == ey && flag) break;
res += abs(ex - x) + abs(ey - y);
x = ex,y = ey;
flag = 1;
}
if(res == 1ll * n * m - k) puts("Yes");
else puts("No");
return 0;
}